The present invention is related to the field of controlling movement for large groups of agents. More specifically, this disclosure presents a method for controlling the movement of a plurality of agents using local, low bandwidth communications.
Over the past few decades, approaches to controlling agents have focused on individual agents and a centralized database. As a result, traditional control of agents and sensors has taken the form of a single mobile agent or a small number of agents using a pre-constructed digital map to aid in path planning and control of the agents or agents. It was necessary to develop a large centralized terrain/environment database to serve as the preconstructed digital map for geometric computations. Typical computations at these centralized databases include determination of shortest path to destination, and routes to destinations. Information relevant to these approaches can be found in U.S. Pat. Nos. 4,119,900; 4,882,694; 5,165,064; and 5,170,351. However, the agent control systems disclosed in each one of these references suffers from one or more of the following disadvantages: 1) the agent is oriented within a fixed surface area; 2) the system only allows for narrow applications of distance-maintenance; 3) the system requires a master station and a means to locate agent; 4) the system requires cameras to locate the mobile agents; 5) the employment of an array of ultrasonic transducers is required on mobile agents; 6) each agent is individually controlled and monitored by a large master station database; and 7) each agent monitors a sector of workspace. Thus, it is desirable to provide a method and apparatus for overcoming these limitations.
The present invention provides a method and apparatus for controlling the movement of a plurality of agents. Specifically, the present invention provides the control mechanism through the use of a signaling mechanism wherein certain criteria of a signal, either explicit (such as information embedded in a signal) or implicit (such as an inherent property of the signal like the transmission power) in order to set up ranges of attraction and repulsion in order to maintain a predetermined distance between the agents.
The present invention provides a method for controlling the movement of a plurality of agents wherein each of one of the plurality of agents has at least one other agent locally spaced at a distance therefrom. Each one of the plurality of agents comprises a means for providing mobility, a means for detecting distance and direction to the at least one other locally spaced agent, and a processor coupled with the means for providing mobility and with the means for detecting distance and direction in order to control the movement of the agent and to process the distances and directions between the agent and the at least one other locally spaced agent.
In one embodiment, the method comprises the steps of determining the distance and direction of each agent from each other agent locally spaced with respect thereto; processing the distances and directions between the agent and each other locally spaced agent; and using a distance-maintenance movement behavior based on the distances and directions between the agent and each other locally spaced agent to maintain a predetermined distance from each other locally spaced agent.
In addition to the above, the method may further comprise the steps of designating one of the plurality of agents to act as a blocking beacon; preventing movement of the agent designated to act as a blocking beacon; and urging agents locally spaced with respect to the agent designated to act as a blocking beacon to move away from it, whereby the agent designated as a blocking beacon acts to repel other agents from its vicinity.
The step of processing the distances between the agent and each other locally spaced agent may be performed by providing an attraction/repulsion map for each agent, including an attraction region and a repulsion region; for each other locally spaced agent, determining, based on the attraction/repulsion map, whether the agent is in the attraction region or the repulsion region with respect to the other locally spaced agent; for each other locally spaced agent, where the agent is in the attraction region of a locally spaced agent, generating a vector representing attraction of the agent toward the locally spaced agent; for each other locally spaced agent, where the agent is in the repulsion region, generating a vector representing the repulsion of the agent from the locally spaced agent; using all of the vectors developed for all of the locally spaced agents to generate a movement vector; and wherein the movement vector is used provide a heading and velocity for the agent in order to perform the step of using a distance-maintenance movement behavior to maintain a predetermined distance from the agent to each other locally spaced agent, thereby providing a distance maintenance movement behavior.
Additionally, the step of processing the distances between the agent and each other locally spaced agent may further include the steps of providing a neutral region to the attraction/repulsion map for each agent; and for each locally spaced agent, where the agent is in the neutral region of a locally spaced agent, generating a vector representing neutrality toward the locally spaced agent.
In a further step, the attraction, repulsion, and neutral region may be configured as generally concentric rings around an agent, with the repulsion region residing closest to the agent, the attraction region residing furthest from the agent, and the neutral region residing between the repulsion region and the attraction region. This aids in causing each one of the plurality of agents to maintain a predetermined distance from each other agent locally spaced therefrom. The regions may be defined as functions that decrease in a particular direction. For example, in the attraction region, the attraction may be tailored such that it becomes stronger with increasing distance, while in the repulsion region, the repulsion may be tailored such that it becomes weaker with increasing distance.
Among the agents, one may be designated as a leader, and the attraction/repulsion map for the leader may be adjusted so that the leader moves further away from the locally spaced agents with the locally spaced agents urged toward the leader, whereby the leader moves away from the other agents and the other agents follow the leader.
The designation of the leader may be triggered by various events such as, for example, when the number of agents provided is insufficient to fill the area while maintaining the predetermined distance from each other. The designation of the leader may also be triggered explicitly by a user command.
The leader designation is defined as what starts the actual process of selecting a leader. The actual selection of a leader may be performed in many ways, a few examples of which include (a) selecting the leader explicitly by a user command, (b) selecting a leader through a random selection process, (c) selecting a leader through a repeated random selection process, and (d) selecting the leader through a biased random selection. The process of selecting a leader may be periodically repeated upon the occurrence of a triggering event. Additionally, once a leader is selected, it may be desirable for the leader to transmit a suppression signal for preventing the repetition of the leader designating step until the occurrence of a triggering event. The suppression signal may be such that it indicates the approximate distance from the leader and such that upon cessation of the transmission of the suppression signal, the random selection process is caused to resume, but is biased in favor of those agents furthest from the leader. In addition, the suppression signal transmitted from the leader may be relayed away from the leader such that it indicates the approximate distance from the leader and is ineffective for preventing the repetition of the leader designating step at a sufficient distance.
In another embodiment, at least one agent may be designated as a reference agent, transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving in a manner determined as a function of the distance estimates of the reference signals. In this way, the agents may be controlled by reference agents to follow a particular path or align in a particular pattern. For example, if two reference agents are used, the other agents may be caused to align in a line equidistant from the reference agents. If three agents are used as references, the other agents may be controlled by using a triangulation-type method.
All of the functions necessary to perform the steps of the method may be incorporated into the circuitry of the agents, in the form of software or hardware. Individual agents or groups of agents may be produced embodying the necessary hardware to accomplish the method.